/*
397. 整数替换
给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1

示例 2:

输入:
7

输出:
4

解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1
*/
/**
 * 解法1：
 * 偶数没说明好说的，
 * 奇数的时候，+1还是-1？
 * 7是一个分界点,7的时候加和减是一样的
 * 7->8->4->2->1
 * 7->6->3->2->1
 * 3的时候，选减的
 * 3->2->1
 * 3->4->2->1
 * 15的时候选加的
 * 15->16->8->4->2->1
 * 15->14->7->8->4->2->1
 * 11也需要像7一样考虑，因为
 * 11->12->6->3->2->1
 * 11->10->5->4->2->1
*/
class Solution
{
public:
    int integerReplacement(int n)
    {
        int          ret = 0;
        unsigned int m = n;
        while(m > 1) {
            if(m & 1) {
                if((m & 7) == 7 || (m & 11) == 11) {
                    m += 1;
                } else {
                    m -= 1;
                }
            } else {
                m /= 2;
            }
            ret++;
        }
        return ret;
    }
};